The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure. Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in the present disclosure and are not admitted to be prior art by inclusion in this section.
Big number squaring may be an integral part of cryptographic operations. For example, the Rivest, Shamir and Adleman (“RSA”) cryptographic algorithm may include two modular exponentiations. A w-ary modular exponentiation algorithm may include a loop that iterates through exponent bits in groups of w bits. In each iteration, w modular squaring operations may be performed, followed by a single modular multiplication operation. A modular squaring operation may include one big integer squaring, plus a number of smaller multiplications and additions that vary depending on the method used. A modular multiplication may include one big integer multiplication, plus several smaller multiplications and additions, again depending on the method used. In some cases the big integer squaring may typically involve integers of 8 or 16 digits, and may consume approximately 40% of the modular squaring operation. For example, with a window size of w=4 (four modular squaring operations per modular multiplication), approximately one third of the exponentiation time may be consumed by the big integer squaring. The relative weight of the big integer squaring operations may increase for larger windows sizes (e.g., w=5, w=6, and so forth).
A big number such as a big integer x may be represented on a computer by t b-bit digits. The number of bits b may be the number of bits in a word on a given architecture, and the number of digits t may be the number of words required to represent the number x. For example, on a 64-bit processor (e.g., x86-64 architecture), an 8-digit number has 512 total bits and a 16-digit number has 1024 bits. An example algorithm for squaring a big number is shown below:
Algorithm 1Input:x = x[0] + x[1]×2b + x[2]×2b ... + x[t−1]×2(t−1)bOutput:w = w[0] + w[1]×2b + w[2]×2b ... + w[2t−1]×2(2t−1)b1.For i from 0 to (2t−1) do: w[i] = 02.For i from 0 to (t−1) do:2.1w[2i] = w[2i] + (x[i]×x[i])low + c2.2w[2i+1] = w[2i+1] + (x[i]×x[i])high + carry2.3c = carry2.4For j from (i+1) to (t−1) do:2.4.1w[i+j] = w[i+j] + (2×x[j]×x[i])low + u2.4.2u = (2×x[j]×x[i])high + carry;2.5w[i+t] = u3.Return w
In the above algorithm, carry may be a carry bit from a most recent add operation performed. c and u may be registers.